package com.enjoy.leetcode;

/**
 * 4. 寻找两个正序数组的中位数 时间复杂度O(log(M+N))
 * num1  [1,3,5,6]
 * num2  [2,5,7,8,23,45]
 *
 * 二分法
 */
public class ch4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 先换个位置保证上面的短，下面的长
        if (nums1.length > nums2.length) {
            int[] tem = nums1;
            nums1 = nums2;
            nums2 = tem;
        }

        int m = nums1.length;
        int n = nums2.length;

        // 在num1的区间[0,m]之间查找
        // 左边
        int left = 0;
        // 右边
        int right = m;

        // 满足左边和右边相等或者左边比右边多1个
        int k = (m + n + 1) / 2;

        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = k - i;
            if (nums1[i - 1] > nums2[j]) {
                // 下一轮搜索的区间[left,i-1]
                right = i - 1;
            } else {
                // 下一轮搜索区间[i,right]
                left = i;
            }

        }
        int i = left;
        int j = k - i;

        int num1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int num1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int num2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int num2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];


        if ((m + n) % 2 == 1) {
            return Math.max(num1LeftMax, num2LeftMax);
        } else {
            return (double) (Math.max(num1LeftMax, num2LeftMax) + Math.min(num1RightMin, num2RightMin)) / 2;
        }

    }

    public static void main(String[] args) {
        ch4 ch4 = new ch4();
        ch4.findMedianSortedArrays(new int[]{1, 3}, new int[]{2, 4});
    }
}
